import java.util.*;

//课程表
//测试链接：https://leetcode.cn/problems/course-schedule/description/
public class CanFinish {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];  //记录每个点入度的度数

        Map<Integer, List<Integer>> edges = new HashMap<>(); //创建邻接表

        for(int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][0], b = prerequisites[i][1];//[a,b]表示b->a学a之前要学b

            if(!edges.containsKey(b)) {
                edges.put(b, new ArrayList<>());
            }
            edges.get(b).add(a);
            in[a]++;
        }

        //开始拓扑排序
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < numCourses; i++) {
            if(in[i] == 0) {  //先将入度为0的点加进队列
                q.add(i);
            }
        }

        while(!q.isEmpty()) {
            int m = q.poll();  //取出入度为0的点

            //删除入度为0的点相邻的边
            for(int n : edges.getOrDefault( m,new ArrayList<>() )) {
                in[n]--;

                //如果该点入度变为0，将其入队列
                if(in[n] == 0) q.add(n);
            }
        }

        //判断是否所有点都变成入度为0了，是否完成了拓扑排序
        for(int x : in)
            if(x != 0) return false;

        return true;
    }
}
